The present invention relates to instruction schedulers and more specifically to dependence graphs used for scheduling instructions.
A dependence graph consists of a set of vertices and directed edges between those vertices. The vertices represent machine instructions or pseudo instructions.
An example of a dependence graph is illustrated in FIG. 1. The four top vertices in the graph (102) represent writes to four distinct locations. The four bottom vertices (104) represent reads, via pointers, that might read any of the four locations. The edges in the graph (106) show the dependences.
In general, for a dependence graph or subgraph having M writes followed by N reads, where M and N are integers, the dependence graph can have up to M×N edges. Thus, a worst case dependence graph will have a number of edges that is quadratic in the number of vertices. This is detrimental, because it takes quadratic time to generate a dependence graph having a quadratic number of edges, and causes instruction scheduling to take quadratic time as well. This is particularly a problem if compilation time is an issue, such as for Just-In-Time (JIT) compilers.